package Algorithm.Array.MinSubArrayLen;

import java.util.ArrayList;

/**
 * @ClassName FruitsInABasket
 * @Description TODO: LEETCODE-904. 水果成篮
 * @Author ykeezy
 * @Date 2024/6/26 22:32
 */
//题目简析：给出一个数组，找到这个数组中最多只包含两种元素的最长子串的长度
    //双指针——滑动窗口法
    //使用一个列表容纳目前可以接收的元素，快指针向数组右边探索直到遇到不在这个列表中的元素
    //若目前列表元素只有1一个，则将新元素加入并继续向后判断
    //若目前列表元素已满(2个)，则结算子串长度后加入新遇到的元素
    //直到遍历完数组
public class FruitsInABasket {
    public static void main(String[] args) {
        System.out.println(totalFruit(new int[]{1,0,1,4,1,4,1,2,3}));

    }

    public static int totalFruit(int[] fruits) {
        int fruitNum = 0;   //最多只包含两种元素的最长子串的长度

        int fastPointer = 0;    //快指针

        int slowPointer = 0;    //慢指针

        int leftFruitCount = 0; //子串排在左边的元素
        ArrayList<Integer> fruitTypes = new ArrayList<>(); //目前可以接收的元素
        //自动装箱
        fruitTypes.add(fruits[0]);
        //快指针从0到数组长度进行遍历
        for (; fastPointer < fruits.length; fastPointer++) {
            //找到目前不可以接收的元素就停下 (不在fruitTypes中的)
            if (!fruitTypes.contains(fruits[fastPointer])) {
                //若fruiTypes.size()不足2说明目前可以接受的元素还可以再加一种
                if (fruitTypes.size() < 2){
                    fruitTypes.add(fruits[fastPointer]);
                    leftFruitCount = fastPointer - slowPointer;
                    slowPointer = fastPointer;
                    //若fruiTypes.size() == 2说明目前可以接收的元素已满，将目前子串并不在最右的元素弹出fruiTypes
                } else if (fruitTypes.size() == 2) {
                    fruitNum = Math.max(leftFruitCount + (fastPointer - slowPointer), fruitNum);
                    leftFruitCount = 0;
                    //弹出目前子串并不在最右的元素
                    fruitTypes.clear();
                    fruitTypes.add(fruits[fastPointer - 1]);
                    //加入遇到的新元素
                    fruitTypes.add(fruits[fastPointer]);
                    //慢指针遍历到和快指针会合，计算目前fruitTypes左边位置元素的有效数量到目前位置有多少
                    while(slowPointer < fastPointer){
                        //自动拆箱
                        if (fruitTypes.get(0) == fruits[slowPointer]) {
                            leftFruitCount++;
                        }else {
                            leftFruitCount = 0;

                        }

                        slowPointer++;

                    }

                }

            }

            /*for(Integer i: fruitTypes){
                System.out.print(i);
            }
            System.out.println();*/

        }

        fruitNum = Math.max(leftFruitCount + (fastPointer - slowPointer), fruitNum);
        return fruitNum;

    }


}
